/**
 * 152. 乘积最大子数组
 * https://leetcode-cn.com/problems/maximum-product-subarray/
 */
public class Solutions_152 {
    public static void main(String[] args) {
//        int[] nums = {2, 3, -2, 4};  // output: 6
//        int[] nums = {-2, 0, -1};  // output: 0
        int[] nums = {-3, 3, -1, 4, -2};  // output: 36

        int result = maxProduct(nums);
        System.out.println(result);
    }

    /**
     * 解法二：正反线性扫描（0ms）
     * 偶数个负数相乘，最终结果还是正数
     */
    public static int maxProduct(int[] nums) {
        // 题目说明：至少包含一个数字
        if (nums.length == 1) {
            return nums[0];
        }
        // 系数为 1，除 0 外，任何数乘 1 都等于其本身
        int a = 1;
        int max = nums[0];
        // 正序遍历一次，计算从左往右遍历时的最大乘积
        for (int num : nums) {
            a = a * num;
            if (a > max) {
                // 记录下最大值
                max = a;
            }
            if (num == 0) {
                // 还原系数为 1
                a = 1;
            }
        }
        a = 1;
        // 倒序遍历一次，计算从右往左遍历时的最大乘积
        for (int i = nums.length - 1; i >= 0; i--) {
            a = a * nums[i];
            if (a > max) {
                // 记录下最大值
                max = a;
            }
            if (nums[i] == 0) {
                // 还原系数为 1
                a = 1;
            }
        }
        return max;
    }

    /**
     * 解法一：动态规划（2ms）
     */
    public static int maxProduct2(int[] nums) {
        int res = Integer.MIN_VALUE, imax = 1, imin = 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) {
                // 出现负数时，那么会导致最大的变最小的，最小的变最大的。因此交换两个的值。
                // 保证 imax 一定是存储的较大值
                int temp = imax;
                imax = imin;
                imin = temp;
            }
            // 当前索引上，能够计算得到的最大值，以及最小值
            // 即保留不保留 i 之前的计算结果的问题，若取 nums[i] 则说明不保留之前计算的结果
            imax = Math.max(nums[i], imax * nums[i]);
            imin = Math.min(nums[i], imin * nums[i]);
            // res 始终记录的是子数组乘积的最大值
            res = Math.max(res, imax);
        }
        return res;
    }
}
